//
// Created by hay boy on 2022/7/6.
//

#ifndef ALGORITHMS_FINDMINIMUMPATH_H
#define ALGORITHMS_FINDMINIMUMPATH_H
#include "../queue/ArrayDeque.h"
#include <iostream>
#include "maze.h"


using namespace std;
position start(3,2);
position finish(4,6);
int** grid;
int size = 7;
int pathLength = 0;
position* path;
bool findPath();
bool findPath(){
    if((start.row==finish.row)&&(start.col==finish.col)){
        pathLength = 0;
        return true;
    }
    position offset[4];
    offset[0].row = 0;offset[0].col = 1;
    offset[1].row = 1;offset[1].col = 0;
    offset[2].row = 0;offset[2].col = -1;
    offset[3].row = -1;offset[3].col = 0;
    grid = new int*[size+2];
    for(int i = 0;i<size+2;i++){
        grid[i] = new int[size];
    }
    for(int i = 0;i<=size+1;i++){
        grid[0][i] = grid[size+1][i] = 1;
        grid[i][0] = grid[i][size+1] = 1;
    }
    for(int i = 1;i<=size;i++){
        for(int j = 1;j<=size;j++){
            grid[i][j] = 0;
        }
    }
    grid[1][3] = grid[2][3] = grid[2][4] = 1;
    grid[3][5] = grid[4][4] = grid[4][5] = 1;
    grid[5][1] = grid[5][5] = 1;
    grid[6][1] = grid[6][2] = grid[6][3] = 1;
    grid[7][1] = grid[7][2] = grid[7][3] = 1;
    position here = start;
    grid[start.row][start.col] = 2;
    int numberOfNbrs = 4;
    ArrayDeque<position> q;
    position nbr;
    do{
        for(int i  = 0;i<numberOfNbrs;i++){
            nbr.row = here.row+offset[i].row;
            nbr.col = here.col+offset[i].col;
            if(grid[nbr.row][nbr.col]==0){
                grid[nbr.row][nbr.col]=grid[here.row][here.col] + 1;
                if((nbr.row==finish.row)&&(nbr.col==finish.col)){
                    break;
                }
                q.push(nbr);
            }
        }
        if((nbr.row==finish.row)&&(nbr.col==finish.col)){
            break;
        }
        if(q.empty()){
            return false;
        }
        here = q.front();
        q.pop();
    }while(true);
    pathLength = grid[finish.row][finish.col] - 2;
    path = new position[pathLength];
    here = finish;
    for(int j = pathLength-1;j>=0;j--){
        path[j] = here;
        inner:
        for(int i = 0;i<numberOfNbrs;i++){
            nbr.row = here.row+offset[i].row;
            nbr.col = here.col+offset[i].col;
            if(grid[nbr.row][nbr.col]==j+2){
                break;
            }
        }
        here = nbr;
    }
    return true;
};
void printPath(){
    for(int i = 0;i<pathLength;i++){
        cout<<path[i].row<<" "<<path[i].col<<endl;
    }
}
#endif //ALGORITHMS_FINDMINIMUMPATH_H
